Approximation Algorithms for Graph Homomorphism Problems
Identifieur interne : 000269 ( Main/Exploration ); précédent : 000268; suivant : 000270Approximation Algorithms for Graph Homomorphism Problems
Auteurs : Michael Langberg [États-Unis] ; Yuval Rabani [Israël] ; Chaitanya Swamy [États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2006.
Abstract
Abstract: We introduce the maximum graph homomorphism (MGH) problem: given a graph G, and a target graph H, find a mapping ϕ:V G ↦V H that maximizes the number of edges of G that are mapped to edges of H. This problem encodes various fundamental NP-hard problems including Maxcut and Max-k-cut. We also consider the multiway uncut problem. We are given a graph G and a set of terminals T ⊆ V G . We want to partition V G into |T| parts, each containing exactly one terminal, so as to maximize the number of edges in E G having both endpoints in the same part. Multiway uncut can be viewed as a special case of prelabeled MGH where one is also given a prelabeling ${\ensuremath{\varphi}}':U\mapsto V_H,\ U{\subseteq} V_G$ , and the output has to be an extension of ϕ′. Both MGH and multiway uncut have a trivial 0.5-approximation algorithm. We present a 0.8535-approximation algorithm for multiway uncut based on a natural linear programming relaxation. This relaxation has an integrality gap of $\frac{6}{7}\simeq 0.8571$ , showing that our guarantee is almost tight. For maximum graph homomorphism, we show that a $\bigl({\ensuremath{\frac{1}{2}}}+{\ensuremath{\varepsilon}}_0)$ -approximation algorithm, for any constant ε 0 > 0, implies an algorithm for distinguishing between certain average-case instances of the subgraph isomorphism problem that appear to be hard. Complementing this, we give a $\bigl({\ensuremath{\frac{1}{2}}}+\Omega(\frac{1}{|H|\log{|H|}})\bigr)$ -approximation algorithm.
Url:
DOI: 10.1007/11830924_18
Affiliations:
Links toward previous steps (curation, corpus...)
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Approximation Algorithms for Graph Homomorphism Problems</title><author><name sortKey="Langberg, Michael" sort="Langberg, Michael" uniqKey="Langberg M" first="Michael" last="Langberg">Michael Langberg</name></author><author><name sortKey="Rabani, Yuval" sort="Rabani, Yuval" uniqKey="Rabani Y" first="Yuval" last="Rabani">Yuval Rabani</name></author><author><name sortKey="Swamy, Chaitanya" sort="Swamy, Chaitanya" uniqKey="Swamy C" first="Chaitanya" last="Swamy">Chaitanya Swamy</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:BC431F35CD0C8DE26A563929569D4C11F875FF77</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/11830924_18</idno><idno type="url">https://api.istex.fr/document/BC431F35CD0C8DE26A563929569D4C11F875FF77/fulltext/pdf</idno><idno type="wicri:Area/Main/Corpus">000440</idno><idno type="wicri:Area/Main/Curation">000440</idno><idno type="wicri:Area/Main/Exploration">000269</idno><idno type="wicri:explorRef" wicri:stream="Main" wicri:step="Exploration">000269</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Approximation Algorithms for Graph Homomorphism Problems</title><author><name sortKey="Langberg, Michael" sort="Langberg, Michael" uniqKey="Langberg M" first="Michael" last="Langberg">Michael Langberg</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Dept. of Computer Science, Caltech, 91125, Pasadena, CA</wicri:regionArea><wicri:noRegion>CA</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Rabani, Yuval" sort="Rabani, Yuval" uniqKey="Rabani Y" first="Yuval" last="Rabani">Yuval Rabani</name><affiliation wicri:level="1"><country xml:lang="fr">Israël</country><wicri:regionArea>Computer Science Dept., Technion — Israel Institute of Technology, 32000, Haifa</wicri:regionArea><wicri:noRegion>Haifa</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Israël</country></affiliation></author><author><name sortKey="Swamy, Chaitanya" sort="Swamy, Chaitanya" uniqKey="Swamy C" first="Chaitanya" last="Swamy">Chaitanya Swamy</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Center for the Mathematics of Information, Caltech, 91125, Pasadena, CA</wicri:regionArea><wicri:noRegion>CA</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2006</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">BC431F35CD0C8DE26A563929569D4C11F875FF77</idno><idno type="DOI">10.1007/11830924_18</idno><idno type="ChapterID">18</idno><idno type="ChapterID">Chap18</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We introduce the maximum graph homomorphism (MGH) problem: given a graph G, and a target graph H, find a mapping ϕ:V G ↦V H that maximizes the number of edges of G that are mapped to edges of H. This problem encodes various fundamental NP-hard problems including Maxcut and Max-k-cut. We also consider the multiway uncut problem. We are given a graph G and a set of terminals T ⊆ V G . We want to partition V G into |T| parts, each containing exactly one terminal, so as to maximize the number of edges in E G having both endpoints in the same part. Multiway uncut can be viewed as a special case of prelabeled MGH where one is also given a prelabeling ${\ensuremath{\varphi}}':U\mapsto V_H,\ U{\subseteq} V_G$ , and the output has to be an extension of ϕ′. Both MGH and multiway uncut have a trivial 0.5-approximation algorithm. We present a 0.8535-approximation algorithm for multiway uncut based on a natural linear programming relaxation. This relaxation has an integrality gap of $\frac{6}{7}\simeq 0.8571$ , showing that our guarantee is almost tight. For maximum graph homomorphism, we show that a $\bigl({\ensuremath{\frac{1}{2}}}+{\ensuremath{\varepsilon}}_0)$ -approximation algorithm, for any constant ε 0 > 0, implies an algorithm for distinguishing between certain average-case instances of the subgraph isomorphism problem that appear to be hard. Complementing this, we give a $\bigl({\ensuremath{\frac{1}{2}}}+\Omega(\frac{1}{|H|\log{|H|}})\bigr)$ -approximation algorithm.</div></front></TEI><affiliations><list><country><li>Israël</li><li>États-Unis</li></country></list><tree><country name="États-Unis"><noRegion><name sortKey="Langberg, Michael" sort="Langberg, Michael" uniqKey="Langberg M" first="Michael" last="Langberg">Michael Langberg</name></noRegion><name sortKey="Langberg, Michael" sort="Langberg, Michael" uniqKey="Langberg M" first="Michael" last="Langberg">Michael Langberg</name><name sortKey="Swamy, Chaitanya" sort="Swamy, Chaitanya" uniqKey="Swamy C" first="Chaitanya" last="Swamy">Chaitanya Swamy</name><name sortKey="Swamy, Chaitanya" sort="Swamy, Chaitanya" uniqKey="Swamy C" first="Chaitanya" last="Swamy">Chaitanya Swamy</name></country><country name="Israël"><noRegion><name sortKey="Rabani, Yuval" sort="Rabani, Yuval" uniqKey="Rabani Y" first="Yuval" last="Rabani">Yuval Rabani</name></noRegion><name sortKey="Rabani, Yuval" sort="Rabani, Yuval" uniqKey="Rabani Y" first="Yuval" last="Rabani">Yuval Rabani</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amerique/explor/CaltechV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000269 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000269 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Amerique
|area= CaltechV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:BC431F35CD0C8DE26A563929569D4C11F875FF77
|texte= Approximation Algorithms for Graph Homomorphism Problems
}}
| This area was generated with Dilib version V0.6.32. |  |